| 翻訳と辞書 |
| Urquhart graph ： ウィキペディア英語版 |
Urquhart graph
In computational geometry, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation.
The Urquhart graph was described by , who suggested that removing the longest edge from each Delaunay triangle would be a fast way of constructing the relative neighborhood graph (the graph connecting pairs of points ''p'' and ''q'' when there does not exist any third point ''r'' that is closer to both ''p'' and ''q'' than they are to each other). Since Delaunay triangulations can be constructed in time O(''n'' log ''n''), the same time bound holds for the Urquhart graph as well.〔.〕 Although it was later shown that the Urquhart graph is not exactly the same as the relative neighborhood graph,〔. Reply by Urquhart, pp. 860–861.〕 it can be used as a good approximation to it.〔.〕 The problem of constructing relative neighborhood graphs in O(''n'' log ''n'') time, left open by the mismatch between the Urquhart graph and the relative neighborhood graph, was solved by .〔.〕
Like the relative neighborhood graph, the Urquhart graph of a set of points in general position contains the Euclidean minimum spanning tree of its points, from which it follows that it is a connected graph.
== References ==
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Urquhart graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|